﻿#include <iostream>
using namespace std;
//大佬写的小堆化
void MinHeapFixDown(int arr[], int i, int sz)
{
	int tmp = arr[i];
	int j = 2 * i + 1; //左孩子
	while (j < sz)
	{
		if (arr[j + 1] < arr[j]) //在左右孩子中找最小的
			j += 1;//小孩子
		if (arr[j] < arr[i])//小孩子比自己还小，则小孩子上浮
		{
			arr[i] = arr[j];
			i = j;  //站到小孩子的位置，大孩子那边可以不管了 
			j = 2 * i + 1;  //指向小孩子的左孩子
		}
		else
			break;
	}
	//循环走完，i的位置就是temp应该放置的位置
	arr[i] = tmp;
}
//我写的小堆化
void MinHeap(int arr[], int i, int sz)
{
	//找到左右孩子
	int left = 2 * i + 1;
	int right = 2 * i + 2;
	//左孩子已经越界了，则右孩子也越界了
	if (left >= sz)
	{
		return;
	}
	//右孩子越界了但左孩子还没有越界
	int min = left;
	if (right >= sz)
	{
		min = left; //此时左孩子就是小孩子
	}
	else
	{
		if (arr[right] < arr[left])
		{
			min = right;
		}
	}
	//此时min指向了左右孩子中的小孩子
	//如果arr[i]小于小孩子，则不用调整，否则和小孩子进行交换
	if (arr[i] < arr[min])return;
	else
	{
		int tmp = arr[i];
		arr[i] = arr[min];
		arr[min] = tmp;
	}
	//小孩子的位置发生了变化，i变更为小孩子的位置，递归调整
	MinHeap(arr, min, sz);
}
//小顶堆
void MakeMinHeap(int arr[], int sz)
{
	for (int i = sz / 2 - 1; i >= 0; i--)
	{
		MinHeap(arr, i, sz);
	}
}
void Sort1(int arr[],int sz)
{
	//先对arr进行堆化
	MakeMinHeap(arr,sz);
	//把堆顶0号元素与最后一个元素对调
	for (int i = sz - 1; i >= 0; i--)
	{
		int tmp = arr[0];
		arr[0] = arr[i];
		arr[i] = tmp;
		//缩小堆的范围，对堆顶元素进行向下调整
		MinHeap(arr, 0, i-1);
	}
}
//大顶堆的写法，类似
void MaxHeap(int arr[], int i, int sz)
{
	int left = 2 * i + 1;
	int right = 2 * i + 2;
	if (left >= sz)return;
	int max = left;
	if (right >= sz)max = left;
	else
	{
		if (arr[right] > arr[left])max = right;
	}
	if (arr[i] > arr[max])return;
	else
	{
		int tmp = arr[i];
		arr[i] = arr[max];
		arr[max] = tmp;
	}
	MaxHeap(arr, max, sz);
}
//大顶堆化
void MakeMaxHeap(int arr[], int sz)
{
	for (int i = sz / 2 - 1; i >= 0; i--)
	{
		MaxHeap(arr, i, sz);
	}
}
void Sort2(int arr[], int sz)
{
	MakeMaxHeap(arr, sz);//先大顶堆化
	for (int i = sz-1; i >= 0; i--)
	{
		int tmp = arr[0];
		arr[0] = arr[i];
		arr[i] = tmp;
		//交换元素后再堆化
		MaxHeap(arr, 0, i-1);
	}
}
int main()
{
	int arr[] = { 9,7,8,10,12,5,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	Sort1(arr, sz);
	for (int i = 0; i < sz; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
	//Sort2(arr, sz);
	//for (int i = 0; i < sz; i++)
	//{
	//	cout << arr[i] << " ";
	//}
	//cout << endl;
}